# This is a sample Python script.
import copy

# Press Shift+F10 to execute it or replace it with your code.
# Press Double Shift to search everywhere for classes, files, tool windows, actions, and settings.
import pandas as pd
import numpy as np
import matplotlib.pyplot as plt
import random
import math
import webbrowser


def domination_sort(cost):
    domination_list = [[] for i in range(len(cost))]
    dominated_no = [0 for i in range(len(cost))]
    front = [[]]
    for i in range(len(cost)):
        for j in range(len(cost)):
            if cost[i][0] <= cost[j][0] and cost[i][1] <= cost[j][1] and not (
                    cost[i][0] == cost[j][0] and cost[i][1] == cost[j][1]):
                domination_list[i].append(j)
                # dominated_no[j] = dominated_no[j] + 1
            elif cost[i][0] >= cost[j][0] and cost[i][1] >= cost[j][1] and not (
                    cost[i][0] == cost[j][0] and cost[i][1] == cost[j][1]):
                dominated_no[i] = dominated_no[i] + 1
                # domination_list[j].append(i)
        if dominated_no[i] == 0:
            front[0].append(i)
    out_dom = copy.deepcopy(dominated_no)
    i = 0
    while front[i]:
        temp = []
        for a in front[i]:
            for b in domination_list[a]:
                dominated_no[b] = dominated_no[b] - 1
                if dominated_no[b] == 0:
                    temp.append(b)
        # print(temp)
        front.append(temp)
        i = i + 1
    # print(front)
    return front, out_dom


def crowd_dis(front, fun_cost, no):
    cost = np.array(fun_cost)
    cost = cost[front]
    dist1 = [0 for i in range(len(front))]
    dist2 = [0 for i in range(len(front))]
    first_index = np.argsort(cost[:, 0])
    second_index = np.argsort(cost[:, 1])
    dist1[first_index[0]] = math.inf
    dist1[first_index[len(front) - 1]] = math.inf
    dist2[second_index[0]] = math.inf
    dist2[second_index[len(front) - 1]] = math.inf
    for i in range(1, len(front) - 1):
        dist1[first_index[i]] = abs(cost[first_index[i - 1], 0] - cost[first_index[i + 1], 0])
        dist2[second_index[i]] = abs(cost[second_index[i - 1], 1] - cost[second_index[i - 1], 1])
    dist = np.add(dist2, dist1)
    front_index = np.argsort(dist)
    new_front = []
    lens = len(front) - 1
    # print(str(len(front))+' '+str(lens)+' '+str(len(front_index)))
    for i in range(no):
        new_front.append(front[front_index[lens - i]])
    return new_front


def find_index(ind_, left, right, val):
    index = math.inf
    # print(len(ind_), " ", left, " ", right)
    for i in range(left):
        if ind_[i] == val:
            index = i
    if right != len(ind_) - 1:
        for i in range(right + 1, len(ind_)):
            if ind_[i] == val:
                index = i - len(ind_)
    # print(len(ind_), " ", left, " ", right)
    return index


def is_legal(ind, cap):
    label = True
    residue = cap
    for i in range(1, len(ind) - 1):
        if ind[i] == 0:
            residue = cap
        elif residue >= data[ind[i], 3]:
            residue = residue - data[ind[i], 3]
        else:
            label = False
    return label


def find_zero(ind, num):
    left = 0
    right = 0
    count = -1
    for i in range(len(ind)):
        if ind[i] == 0:
            count = count + 1
            if count == num:
                left = i
            elif count == num + 1:
                right = i
    return left, right


def mutation(ind):  #
    index1 = random.randint(1, len(ind) - 2)
    index2 = random.randint(1, len(ind) - 2)
    while ind[index1] == 0:
        index1 = random.randint(1, len(ind) - 2)
    while ind[index2] == 0:
        index2 = random.randint(1, len(ind) - 2)
    temp = ind[index1]
    ind[index1] = ind[index2]
    ind[index2] = temp
    return ind


def crossover_and_mutation(old_pop):
    legal_pop_ = []
    illegal_pop = []
    for i in range(round(PopSize / 2)):
        index1 = random.randint(0, len(old_pop) - 1)
        index2 = random.randint(0, len(old_pop) - 1)
        while index1 == index2:
            index2 = random.randint(0, len(old_pop) - 1)
        father1 = copy.deepcopy(old_pop[index1])
        father2 = copy.deepcopy(old_pop[index2])
        father1_num = father1.count(0)
        father2_num = father2.count(0)
        father1_index = random.randint(0, father1_num - 2)
        father2_index = random.randint(0, father2_num - 2)
        index_1_f, index_1_r = find_zero(father1, father1_index)
        index_2_f, index_2_r = find_zero(father2, father2_index)
        father1_long = index_1_r - index_1_f
        father2_long = index_2_r - index_2_f
        if father2_long > father1_long:
            gene_long = father1_long - 1
            # index_2_r = gene_long + index_2_f
        else:
            gene_long = father2_long - 1
            # index_1_r = gene_long + index_1_f
        # print(gene_long)
        gene_long = random.randint(1, gene_long)
        up = copy.deepcopy(father1[index_1_f + 1:index_1_f + 1 + gene_long])
        if random.random() < 0.5:
            down = copy.deepcopy(father2[index_2_f + 1:index_2_f + 1 + gene_long])
            father1[index_1_f + 1:index_1_f + 1 + gene_long] = down
            father2[index_2_f + 1:index_2_f + 1 + gene_long] = up
        else:
            down = copy.deepcopy(father2[index_2_r - gene_long:index_2_r])
            father1[index_1_f + 1:index_1_f + 1 + gene_long] = down
            father2[index_2_r - gene_long:index_2_r] = up
        for seat in range(len(up)):
            index = find_index(father2, index_2_f, index_2_r, up[seat])
            if index != math.inf:
                father2[index] = down[seat]
        for seat in range(len(down)):
            index = find_index(father1, index_1_f, index_1_r, down[seat])
            if index != math.inf:
                father1[index] = up[seat]
        # print(len(father1),len(father2))
        if random.random() < 0.5:
            # new_son = mutation(old_pop[random.randint(0, Pop_size - 1)])
            # new_pop_.append(new_son)
            mut_index = random.randint(0, len(old_pop) - 1)
            mut_father1 = old_pop[mut_index]
            mut_son = mutation(mut_father1)
            if is_legal(mut_son, veh_cap):
                legal_pop_.append(mut_son)
            else:
                illegal_pop.append(mut_son)

        if is_legal(father1, veh_cap):
            legal_pop_.append(father1)
        else:
            illegal_pop.append(father1)
        if is_legal(father2, veh_cap):
            legal_pop_.append(father2)
        else:
            illegal_pop.append(father2)
    return legal_pop_, illegal_pop


def initialize(ini_pop_size, ini_userlen, ini_data, ini_cap):
    i_pop = []
    for i in range(ini_pop_size):
        order = random.sample(range(1, ini_userlen), ini_userlen - 1)
        residue = ini_cap
        temp_pop = [0]
        for j in range(ini_userlen - 1):
            if residue >= ini_data[order[j], 3]:
                residue = residue - ini_data[order[j], 3]
                temp_pop.append(order[j])
            else:
                temp_pop.append(0)
                residue = ini_cap - ini_data[order[j], 3]
                temp_pop.append(order[j])
        temp_pop.append(0)
        i_pop.append(temp_pop)
    return i_pop


def fun_eval(pop):  # 计算目标值
    obj_value = [[] for i in range(len(pop))]
    for i in range(len(pop)):
        obj11 = pop[i].count(0) - 1
        obj12 = 0
        obj2 = 0
        time_ = 0
        for j in range(len(pop[i]) - 1):
            if pop[i][j] != 0:
                obj2 = obj2 + abs(data[pop[i][j], 4] - time_) + abs(data[pop[i][j], 5] - time_) \
                       - abs(data[pop[i][j], 5] - data[pop[i][j], 4])
                time_ = time_ + data[pop[i][j], 6]
                if pop[i][j + 1] != 0:
                    value1 = data[pop[i][j], 1] - data[pop[i][j + 1], 1]
                    value2 = data[pop[i][j], 2] - data[pop[i][j + 1], 2]
                    value = math.sqrt(value1 ** 2 + value2 ** 2)
                    obj12 = obj12 + value
            else:
                time_ = 0
        obj12 = obj12 / obj11
        obj11 = obj11 * 100
        obj1 = obj11 + obj12
        obj_value[i].append(obj1)
        obj_value[i].append(obj2)
    return obj_value


def fun_con(pop):  # 计算约束违反情况
    obj_value = []
    for i in range(len(pop)):
        obj2 = 0
        time_ = 0
        for j in range(len(pop[i]) - 1):
            if pop[i][j] != 0:
                obj2 = obj2 + abs(data[pop[i][j], 4] - time_) + abs(data[pop[i][j], 5] - time_) \
                       - abs(data[pop[i][j], 5] - data[pop[i][j], 4])
                time_ = time_ + data[pop[i][j], 6]
            else:
                time_ = 0
        obj_value.append(obj2)
    return obj_value


def fun_eval_2(pop):  # 计算目标值
    obj_value = [[] for i in range(len(pop))]
    for i in range(len(pop)):
        obj2 = pop[i].count(0) - 1
        obj1 = 0
        for j in range(len(pop[i]) - 1):
            if pop[i][j] != 0 and pop[i][j + 1] != 0:
                value1 = data[pop[i][j], 1] - data[pop[i][j + 1], 1]
                value2 = data[pop[i][j], 2] - data[pop[i][j + 1], 2]
                value = math.sqrt(value1 ** 2 + value2 ** 2)
                obj1 = obj1 + value
        obj_value[i].append(obj1)
        obj_value[i].append(obj2)
    return obj_value


def evolution(old_pop, old_cost, pop_size, sorted_index):
    surplus = pop_size
    front_no = 0
    sub_pop = []
    sub_cost = []
    while surplus > len(sorted_index[front_no]):
        for i in range(len(sorted_index[front_no])):
            # print(len(Pop[sorted_index[front_no][i]]))
            sub_pop.append(old_pop[sorted_index[front_no][i]])
            sub_cost.append(old_cost[sorted_index[front_no][i]])
        surplus = surplus - len(sorted_index[front_no])
        front_no = front_no + 1
    front_id = crowd_dis(sorted_index[front_no], old_cost, surplus)
    for i in range(surplus):
        sub_pop.append(old_pop[front_id[i]])
        sub_cost.append(old_cost[front_id[i]])
    return sub_pop, sub_cost


def tournament(to_popsize, to_dom_no, demand_no, total_no):
    index = []
    candidate = random.sample(range(to_popsize), total_no)
    can_dom_no = to_dom_no[candidate]
    min_index = np.argsort(can_dom_no)
    for i in range(demand_no):
        index.append(candidate[min_index[i]])
    return index


def find_max_car(ind):
    pointer = 0
    left = 0
    right = 0
    count = 0
    seat = []
    dis = 0
    for i in range(len(ind)):
        if ind[i] == 0:
            count = count + 1
            seat.append(i)
            if count % 2 == 1:
                pointer = i
            elif i - pointer > dis:
                dis = i - pointer
                right = i
                left = pointer
    index = left + round((right - left) / 2) + 1
    return index, seat, count


def insert_car(in_pop, in_popsize, in_dominated_no, if_mult):
    # if empty:
    out_pop = []
    # else:
    # out_pop, out_cost = evolution(in_pop, in_cost, round(in_popsize / 3), in_sorted_index)
    arr_dominated_no = np.array(in_dominated_no)
    while len(out_pop) < in_popsize:
        if if_mult:
            father_index = tournament(in_popsize, arr_dominated_no, 2, 5)
            father1 = copy.deepcopy(in_pop[father_index[0]])
            father2 = copy.deepcopy(in_pop[father_index[1]])
        else:
            father_index = random.sample(range(in_popsize - 1), 2)
            father1 = copy.deepcopy(in_pop[father_index[0]])
            father2 = copy.deepcopy(in_pop[father_index[1]])

        # father1 取最大区间中间插入一个0，
        insert_index, zero_seat, car_no = find_max_car(father1)
        if father1[insert_index] != 0 and father1[insert_index - 1] != 0:
            father1.insert(insert_index, 0)
        # ，father2 取均匀区间插0
        insert_index, zero_seat, car_no = find_max_car(father2)
        father2 = np.array(father2)
        father2 = np.delete(father2, zero_seat)
        # print(father2)
        gap = len(father2) / car_no
        if gap % 1 > 0.5:
            gap = gap - 0.5
        gap = round(gap)
        new_seat = []
        for a in range(car_no):
            num = gap * a
            new_seat.append(num)
        father2 = np.insert(father2, new_seat, 0).tolist()
        father2.append(0)

        # print(new_seat)
        out_pop.append(father1)
        out_pop.append(father2)
    return out_pop


if __name__ == '__main__':
    file = 'c204.txt'  # c204
    data = np.loadtxt(file)
    PopSize = 100
    illegal_popsize = 100
    MaxVehicle = 50
    veh_cap = 200
    User_num = len(data)
    Pop = initialize(PopSize, User_num, data, veh_cap)
    ill_pop = initialize(illegal_popsize, User_num, data, veh_cap)
    legal_pop = []
    cost = fun_con(Pop)
    sort = np.argsort(cost)
    sort_index = 0
    while cost[sort[sort_index]] == 0:
        legal_pop.append(copy.deepcopy(Pop[sort[sort_index]]))
        sort_index = sort_index + 1
    ill_cost = fun_con(ill_pop)
    # sorted_index, dominated_no = domination_sort(cost)
    First_gen = 100
    Second_gen = 300
    gen_no = 1
    plt.ion()  # 开启交互模式
    plt.subplots()
    is_empty = True
    is_full = False

    while not is_full:
        while gen_no < First_gen:
            new_pop, new_ill_pop = crossover_and_mutation(Pop + ill_pop)
            new_cost = fun_con(new_pop)
            new_ill_cost = fun_con(new_ill_pop)
            sort = np.argsort(new_cost)
            sort_index = 0
            while sort_index < len(sort) and new_cost[sort[sort_index]] == 0:
                legal_pop.append(copy.deepcopy(new_pop[sort[sort_index]]))
                sort_index = sort_index + 1
            if len(legal_pop) >= PopSize:
                is_full = True
            Pop = Pop + new_pop
            cost = cost + new_cost
            sort = np.argsort(cost)
            Pop = np.array(Pop)
            cost = np.array(cost)
            Pop = Pop[sort[0:PopSize - 1]].tolist()
            cost = cost[sort[0:PopSize - 1]].tolist()
            ill_pop = ill_pop + new_ill_pop
            ill_cost = ill_cost + new_ill_cost
            ill_pop = np.array(ill_pop)
            ill_cost = np.array(ill_cost)
            sort = np.argsort(ill_cost)
            ill_pop = ill_pop[sort[0:PopSize - 1]].tolist()
            ill_cost = ill_cost[sort[0:PopSize - 1]].tolist()
            gen_no = gen_no + 1
        gen_no = 1
        Pop = insert_car(Pop, len(Pop), None, False)
        ill_pop = insert_car(ill_pop, illegal_popsize, None, False)
        cost = fun_con(Pop)
        ill_cost = fun_con(ill_pop)
        sort = np.argsort(cost)
        sort_index = 0
        while cost[sort[sort_index]] == 0:
            legal_pop.append(copy.deepcopy(Pop[sort[sort_index]]))
            sort_index = sort_index + 1
        if len(legal_pop) >= PopSize:
            is_full = True
    cost = fun_eval(Pop)
    ill_cost = fun_eval(ill_pop)
    legal_cost = fun_eval(legal_pop)
    while gen_no < Second_gen:
        if gen_no % 20 == 0:
            legal_cost = fun_eval(legal_pop)
            use_cost = fun_con(legal_pop)
            index = np.argsort(use_cost)
            legal_pop = np.array(legal_pop)
            legal_pop = legal_pop[index[0:PopSize]].tolist()
            legal_cost = fun_eval(legal_pop)

        new_pop, new_ill_pop = crossover_and_mutation(Pop + ill_pop + legal_pop)
        new_cost = fun_eval(new_pop)
        function = np.array(new_cost)
        function = np.transpose(function, [1, 0])
        for ind in range(len(new_pop)):
            if function[1, ind] == 0:
                legal_pop.append(copy.deepcopy(new_pop[ind]))

        cost = cost + new_cost
        Pop = Pop + new_pop
        sorted_index, dominated_no = domination_sort(cost)
        Pop, cost = evolution(Pop, cost, PopSize, sorted_index)

        new_ill_cost = fun_eval(new_ill_pop)

        ill_cost = ill_cost + new_ill_cost
        ill_pop = ill_pop + new_ill_pop
        ill_sorted_index, ill_dominated_no = domination_sort(ill_cost)
        ill_pop, ill_cost = evolution(ill_pop, ill_cost, illegal_popsize, ill_sorted_index)

        legal_function = np.array(legal_cost)
        legal_function = np.transpose(legal_function, [1, 0])
        function = np.array(cost)
        function = np.transpose(function, [1, 0])
        ill_function = np.array(ill_cost)
        ill_function = np.transpose(ill_function, [1, 0])
        plt.clf()  # 清空画布
        plt.title(gen_no)
        plt.xlabel('Function 1', fontsize=15)
        plt.ylabel('Function 2', fontsize=15)
        plt.scatter(function[0], function[1], c='b')
        plt.scatter(ill_function[0], ill_function[1], c='r')
        # plt.scatter(legal_function[0], legal_function[1], c='g')
        plt.pause(0.2)
        gen_no = gen_no + 1

    finally_cost = fun_eval_2(legal_pop)

    # 第二阶段 扩充可行解
    # while not is_full:
    #     while gen_no < Second_gen:
    #         new_pop, new_ill_pop = crossover_and_mutation(Pop + legal_pop)
    #         new_cost = fun_eval(new_pop)
    #         for ind in range(len(new_pop)):
    #             if function[1, ind] == 0:
    #                 legal_pop.append(copy.deepcopy(Pop[ind]))
    #         if len(legal_pop) >= PopSize:
    #             is_full = True
    #         gen_no = gen_no + 1
    #     gen_no = 1
    front_ = sorted_index[0]  # front_存储前沿个体在pop中的位置
    function = np.array(finally_cost)
    function = np.transpose(function, [1, 0])
    # plt.pause(0.2)
    figure2 = plt.figure()
    #figure2.scatter(function[0], function[1], c='g')
    plt.scatter(function[0], function[1], c='g')
    # for p in range(Pop_size):
    #    function1.append(cost[p][0])
    #    function2.append(cost[p][1])
    Ind_index = []
    for aa in range(0, len(front_)):
        # for aa in range(0,3):
        print(Pop[aa])
    plt.ioff()
    plt.show()
# See PyCharm help at https://www.jetbrains.com/help/pycharm/
